package Top200;

/**
 * @author zhangmin
 * @create 2022-02-17 14:51
 * 递归
 */
public class isMatch10 {
    boolean isMat(String s,int i,String p,int j){
        int ns=s.length(),np=p.length();
        if (j==np){
            //p串到达最后，直接判断s是否到最后
            return i==ns;
        }
        if (i==ns){
            //s串到最后，需要判断p后面的部分是否可以匹配空串,即为a*b*..模式
            if ((np-j)%2==1) return false;
            for (j = j+1;  j< np; j+=2) {
                if (p.charAt(j)!='*') return false;
            }
            return true;
        }
        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
            if (j+1<np&&p.charAt(j+1)=='*'){
                //1、当前字符可以匹配0次或多次
                res=isMat(s,i+1,p,j)||isMat(s,i,p,j+2);
            }else {
                //2、当前字符只能匹配当前的p
                res=isMat(s,i+1,p,j+1);
            }
        }else {
            if (j+1<np&&p.charAt(j+1)=='*'){
                //3、相当于当前字符于后一位的*一起匹配0次
                res=isMat(s,i,p,j+2);
            }else {
                //4、匹配不来
                res=false;
            }
        }
        return res;
    }
    public boolean isMatch(String s, String p) {
        return isMat(s,0,p,0);
    }
}
